Sum of the number of subsets of a subset
The sum of the number of subsets of a subset of a set of size N is $ 3^N
The number of subsets of a set of size k is $ 2^k
How many subsets of size k are there in a set of size N → Combination of choosing k from N
Use binomial theorem in reverse
$ \sum_{k=0}^N \binom{N}{k} 2^k = \sum_{k=0}^N \binom{N}{k} 2^k 1^{N-k} = (2 + 1)^N= 3^N
---
This page is auto-translated from /nishio/部分集合の部分集合の数の和. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.